home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor2 / allf.doc < prev    next >
Text File  |  1995-03-31  |  4KB  |  88 lines
  1.        ALLF by Joseph K. Horn   --   An HP 48 Number Theory tool 
  2.          Calculates ALL the factors (prime and composite) of x 
  3.                      Dedicated to Dr. Robert Wilson 
  4.  
  5. +-------------------------------------------------------------------------+ 
  6. | NOTE:  This program calls FACTOR, a program by Jurjen NE Bos, available | 
  7. | on EduCALC Goodies Disk #2.  You must be in the FACTOR directory when   | 
  8. | you upload ALLF, or it will not work.                                   | 
  9. +-------------------------------------------------------------------------+ 
  10.  
  11. Finding the factors of a number can be done by brute search for small 
  12. numbers, but that takes too long for large numbers.  The following 
  13. program is optimized for speed with large inputs.  For example, it takes 
  14. an input of 842632 and only 1.5 seconds later it returns all 36 factors 
  15. (viz. 1 2 4 7 8 14 28 41 56 82 164 287 328 367 574 734 1148 1468 2296 
  16. 2569 2936 5138 10276 15047 20552 30094 60188 105329 120376 210658 421316 
  17. 842632).  Is there a faster way? 
  18.  
  19. INSTRUCTIONS:  Place a real or binary integer in level 1 and press ALLF. 
  20. The result will be a list of its factors tagged with their count.  For 
  21. example, type 28 and press ALLF and see 6: { 1 2 4 7 14 28 } which means 
  22. that 28 has 6 factors, followed by the list of them. 
  23.  
  24. %%HP:T(3); 
  25. @ ALLF by Joseph K. Horn 
  26. @ Finds ALL the factors (prime & composite divisors) of x. 
  27. @ Uses FACTOR by Jurjen NE Bos. 
  28. @ Input: positive integer.  Output: n:{f1,f2,f3,...,fn}. 
  29. \<< FACTOR OBJ\-> 
  30.   IF DUP 
  31.   THEN { 1 } [ 1 ] ROT 2 + 3 1 \-> p 
  32.     \<< 
  33.       FOR n n ROLL 
  34.         IF DUP p \=/ 
  35.         THEN SWAP DROP OVER OBJ\-> \->ARRY SWAP DUP 'p' STO 
  36.         END * DUP OBJ\-> EVAL \->LIST ROT SWAP + SWAP -1 
  37.       STEP 
  38.     \>> DROP OBJ\-> EVAL DUP DUP 2 + ROLLD \->LIST SWAP \->TAG 
  39.   ELSE DROP :1: { 1 } 
  40.   END 
  41. \>> 
  42.  
  43. ---------- 
  44.  
  45. Note: The factor list is sometimes in numerical order, but that's 
  46. accidental.  If you want to sort it into order every time, be my guest. 
  47. If you own Jim Donnelly's Tool Library, you can use this little routine 
  48. to call ALLF and sort the output: 
  49.  
  50. %%HP:T(3); 
  51. @ FSORT by Joe Horn; uses ALLF and Donnelly's Tool Library. 
  52. \<< ALLF OBJ\-> SWAP OBJ\-> EVAL QSORT \->LIST SWAP \->TAG \>> 
  53.  
  54. INSTRUCTIONS: Same as ALLF, but output is always in order. 
  55.  
  56. ---------- 
  57.  
  58. Number theorists use lowercase-sigma-sub-zero(n) or d(n) to stand for 
  59. the number of factors of n, and lowercase-sigma-sub-one(n) to stand for 
  60. the sum of the factors of n.  A quick and dirty program to generate 
  61. these functions for any input is: 
  62.  
  63. %%HP:T(3); 
  64. @ SIG01 by Joe Horn; uses ALLF. 
  65. \<< ALLF LIST\-> DUP "\Gs0" \->TAG          @ sig0 
  66. OVER 2 + ROLLD \->ARRY CNRM "\Gs1" \->TAG   @ sig1 
  67. \>> 
  68.  
  69. INSTRUCTIONS: Enter x, press SIG01.  See sig0(x) and sig1(x). 
  70. Example: 28 SIG01  -->  sig0: 6 (in level 2), sig1: 56 (in level 
  71. 1).  This means that 28 has 6 divisors, which add up to 56. 
  72.  
  73. Note: These programs, together with PHI posted previously, totally 
  74. replace and extend the TOTIENT tables in the CRC Standard Mathematical 
  75. Tables handbook. 
  76.  
  77. The ancient Greeks enjoyed playing with numbers, and invented the 
  78. concepts of Perfect, Abundant, and Deficient Numbers.  "Perfect 
  79. numbers" are those for which sig1(x)=2x.  "Deficient numbers" are 
  80. those for which sig1(x)<2x.  "Abundant numbers" are those for 
  81. which sig1(x)>2x.  A more recent concept is the "Wierd Number", 
  82. defined as those abundant numbers which have the wierd property 
  83. of being unable to produce 2x by the sum of any subset of x's 
  84. divisors.  A program to check the wierdness of a number is left 
  85. as an exercise to the student... 
  86.  
  87. -Joseph K. Horn-    -Peripheral Vision, Ltd.- 
  88.